package day_2022_4_to_7.day48;

import java.util.Scanner;

/**
 * 走方格的方案数
 * @author haomin
 * @date 2022/04/27 17:01
 **/
public class Day9_2_WalkGridWays {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int rol = in.nextInt();
        int col = in.nextInt();
        System.out.println(fun(rol,col));
        System.out.println(fun2(rol,col));
    }

    // 方法一：递归
    private static int fun(int rol, int col) {
        if(rol == 0 || col == 0){
            return 1;
        }
        return fun(rol-1,col) + fun(rol,col-1);
    }

    // 方法二：迭代
    private static int fun2(int rol,int col){
        int[][] dp = new int[rol+1][col+1];
        for(int i=0; i<=rol; i++) {
            for(int j=0; j<=col; j++) {
                if(i == 0 && j == 0) {
                    dp[i][j] = 1;
                    continue;
                }

                if(i == 0)
                    dp[i][j] = dp[i][j-1];
                else if(j == 0)
                    dp[i][j] = dp[i-1][j];
                else
                    dp[i][j] = dp[i][j-1] + dp[i-1][j];
            }
        }
        return dp[rol][col];
    }
}